package binary;

import java.util.Objects;

/**
 * leet-code(35) 搜索插入位置
 * https://mp.weixin.qq.com/s/1ExIav9uK4bvVnnf4t0H2Q
 *
 * @auther yang
 * @date 2022/3/17 11:41
 */
public class SearchInsert {

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 5;
        System.out.println(searchInsert(nums, target));
    }

    public static int searchInsert(int[] nums, int target) {
        if (Objects.isNull(nums) || nums.length < 1)
            return 0;
        return search(nums, target, 0, nums.length - 1);
    }

    // ======================================================================
    // 递归算法
    // ======================================================================

    private static int search(int[] a, int target, int lo, int hi) {
        if (lo > hi) return lo;
        int mid = lo + ((hi - lo) >> 1);
        if (a[mid] == target) return mid;
        else if (a[mid] < target) return search(a, target, mid + 1, hi);
        else return search(a, target, lo, mid - 1);
    }


    // ======================================================================
    // 非递归算法
    // ======================================================================
    private static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (a[mid] == target) return mid;
            else if (a[mid] > target) hi = mid - 1;
            else lo = mid + 1;
        }
        return lo;
    }
}
